Từ năm 1809, tỉnh này bao gồm năm huyện (uyezd): Kherson, Aleksandria, Ovidiopol, Tiraspol và Yelisavetgrad. Thành phố Odessa mang một vị thế đặc biệt. Năm 1825, huyện Odessa và năm 1834, huyện Ananyev được bổ sung vào bộ phận lãnh thổ của tỉnh Kherson. Huyện thứ bảy là Bobrynets tồn tại từ năm 1828 đến năm 1865. Các thành phố Odessa và Nikolayev (năm 1803–1861) và vùng lân cận được quản lý riêng: Odessa do một gradonachalnik (tiếng Nga: градоначальник) chịu trách nhiệm trực tiếp trước sa hoàng và (từ năm 1822) trước Toàn quyền Novorossiya và Bessarabia, còn Nikolayev do một thống đốc quân sự quản lý.

Năm 1920, dưới sự cai trị của những người Bolshevik, lãnh thổ của tỉnh này rộng 70.600 km² được chia tách để thành lập tỉnh Odessa mới. Tỉnh Kherson còn lại được đổi tên thành tỉnh Mykolaiv (Nikolayev) vào năm 1921, và năm 1922 được sáp nhập với tỉnh Odessa. Năm 1925, tỉnh Odessa bị bãi bỏ và lãnh thổ của nó được chia thành sáu okruha: Kherson, Kryvyi Rih, Mykolaiv, Odessa, Pershotravneve và Zinoviivske.